package lhc.alg.top100;

import java.util.List;

/**
 * description: https://leetcode.cn/problems/triangle/
 *  三角形最小路径和 动态规划 O(n^2) O(n^2) 可做状态压缩 背题怪的一天。。。
 * author: hongchen.liao
 * date:  2022/8/28
 */
public class _120_Triangle {

    class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int n = triangle.size();
            int[][] f = new int[n][n];
            f[0][0] = triangle.get(0).get(0);
            for(int i = 1; i < n; ++i){
                f[i][0] = f[i-1][0] + triangle.get(i).get(0);
                for(int j = 1; j < i; ++j){
                    f[i][j] = Math.min(f[i-1][j-1], f[i-1][j]) + triangle.get(i).get(j);
                }
                f[i][i] = f[i-1][i-1] + triangle.get(i).get(i);
            }
            int minTotal = f[n-1][0];
            for(int i = 1; i < n; ++i){
                minTotal = Math.min(minTotal , f[n-1][i]);
            }
            return minTotal;
        }
    }

}
